package leetcode.easy.q160;

/**
 * 160 相交链表 { @link https://leetcode.cn/problems/intersection-of-two-linked-lists/ }
 */

import leetcode.util.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode(int x) {
 * val = x;
 * next = null;
 * }
 * }
 */
public class Solution {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        return method1(headA, headB);//如果不相交
    }

    /**
     * 双层loop:log(n2)
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode method1(ListNode headA, ListNode headB) {
        ListNode nodeA = headA, nodeB = headB;
        while (nodeA != null) {
            nodeB = headB;
            while (nodeB != null) {
                System.out.println(nodeA + "--" + nodeB);
                if (nodeB != nodeA) {
                    nodeB = nodeB.next;
                    continue;
                }
                return nodeB;
            }
            nodeA = nodeA.next;
        }
        return null;
    }

    /**
     * 法2 hash
     *
     * @return
     */
    public ListNode method2(ListNode headA, ListNode headB) {
        Set<ListNode> nodes = new HashSet<>();
        for (ListNode n = headA; n != null; n = n.next) {
            nodes.add(n);
        }
        for (ListNode n = headB; n != null; n = n.next) {
            if (nodes.contains(n)) return n;
        }
        return null;
    }

    /**
     * 法3  双指针
     * 时间O(m+n) 空间O(1)
     */
    public ListNode method3(ListNode headA, ListNode headB) {
        ListNode nodeA = headA, nodeB = headB;
        while (nodeA != nodeB) {
            nodeA = nodeA == null ? headB : nodeA.next;
            nodeB = nodeB == null ? headA : nodeB.next;
        }
        return nodeA;
    }

}